package jianzhioffer;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/21 21:19
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 */
public class offer_40_最小的k个数 {

    public static void main(String[] args) {
        int[] arr = {4, 5, 1, 6, 2, 7, 3, 8};
        int k = 4;
        int[] res = getLeastNumbers(arr, k);
        System.out.println(Arrays.toString(res));
    }

//    先排序，然后再输出前几个最小值（暴力法，不建议，效率低）
    public static int[] getLeastNumbers1(int[] arr, int k) {
        for (int i=0; i<arr.length; i++){
            for (int j=i+1; j<arr.length; j++){
                if (arr[j]<arr[i]){
                    int tem = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tem;
                }
            }
        }
        int[] res = new int[k];
        for (int l=0; l<k; l++)
            res[l] = arr[l];
        return res;
    }

//    先排序，快速排序
    public static int[] getLeastNumbers2(int[] arr, int k) {
        quickSort(arr, 0, arr.length-1);
        return Arrays.copyOf(arr, k);
    }

    public static void quickSort(int[] arr, int l, int r){
        if (l >= r) return;
        int i = l, j = r;
        while (i<j){
            while (i<j&&arr[j] >= arr[l]) j--;
            while (i<j&&arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        quickSort(arr, l, i-1);
        quickSort(arr, i+1, r);
    }

    public static void swap(int[] arr, int i, int j){
        int tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
    }

    //    在上面快速排序的基础上不需要全部排序，只需要找前k个最小值
    public static int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr, k, 0, arr.length - 1);
    }

    private static int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }

}
